package zuo.from0516.other.day07;

import zuo.from0516.other.day06.TreeNode;

import java.util.*;

/**
 * Q107:二叉树的层序遍历II（中等）
 * 给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。
 * （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：[[15,7],[9,20],[3]]
 * 思路：准备一个队列：
 *  1）先把头结点放到队列中
 *  2）拿出此时队列的size，size有多少，就执行3）多少次
 *  3）取出当前节点放入当前list中，先左后右放入队列中
 */
public class Code01_BinaryTreeLevelOrderTraversalII {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ans  = new LinkedList<>();
         if(root == null){
             return null;
         }
         Queue<TreeNode> queue  = new LinkedList<>();//queue是个接口，不能实例化，linked list是个类，stack是个类，其在Java中的实现比较慢
         queue.add(root);
         while(!queue.isEmpty()){
             int size = queue.size();
             List<Integer> curAns = new LinkedList<>();
             for (int i = 0; i < size; i++) {
                 TreeNode curNode = queue.poll();
                 curAns.add(curNode.value);
                 if (curNode.left != null){
                     queue.add(curNode.left);
                 }
                 if(curNode.right != null){
                     queue.add(curNode.right);
                 }
             }
             ans.add(0,  curAns);
         }
         return ans;
    }
}
